package com.hyper_yang.algorithmRecord;

import java.util.LinkedList;

public class LeetCode_518 {
//    给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
//    请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
//    假设每一种面额的硬币有无限个。
//    题目数据保证结果符合 32 位带符号整数。
//      change(int amount, int[] coins)
    public static void main(String[] args) {
        System.out.println(change(5, new int[]{1, 2, 5}));
    }
    public static int change(int amount, int[] coins) {
        return rec(0, coins, amount, new LinkedList<>(), true);
    }

    public static int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first){
        int count = 0;
        if (!first) stack.push(coins[index]);
        // index: 当前硬币索引    coins: 硬币面值数组   remainder: 剩余金额
        if (remainder < 0) { // remainder < 0 无解
            System.out.println("无解: " + stack); 
        } else if (remainder == 0) { // remainder == 0 解
            System.out.println("有解: " + stack);
        } else { // remainder > 0 继续递归
            for (int i = index; i < coins.length; i++) {
                count += rec(i, coins, remainder-coins[i], stack, false);
            }
        }
        if (!stack.isEmpty()) stack.pop();
        return count;
    }
}
/* eg:
    输入：amount = 5, coins = [1, 2, 5]
    输出：4
    解释：有四种方式可以凑成总金额：
    5=5
    5=2+2+1
    5=2+1+1+1
    5=1+1+1+1+1
 */